/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 刘柄华
 * Date: 2022-05-23
 * Time: 23:34
 */
/*
* 青蛙跳台阶 进阶问题
*
* 思路:  当青蛙只能一次跳1阶或者两阶时 , 当有5阶时,我可以先跳1阶,那么剩下4阶就是 4阶的条法, 也可以先跳两阶,剩下的3阶就是就 3阶的跳法.
*      那么 当青蛙一次能跳1阶 2阶 ...n阶时, 先跳1阶,剩下n-1阶的跳法 , 跳两阶 剩下n-2阶的跳法 ...跳n-1阶, 剩下n-n-1的跳法 ,跳n阶 剩下n-n的跳法
*      f(n) = f(n-1)+f(n-2)+f(n-3)+....+f(n-n-1)+f(n)
*      把表达式倒过来 f(n) = f(0) + f(1) + f(2) +...+ f(n-2) +f(n-1)
*
*       同理 f(n-1) = f(n-2)+f(n-3)+...f(0)   =  f(0) + f(1)+...+f(n-2);
*       把f(n-1)带入到f(n)中  得到 f(n) = 2*f(n-1)
* */
public class TestDemo03 {
    public static int qingWa(int n){
        if(n==0){
            return 1;
        }
        if(n==1){
            return 1;
        }
        return 2*qingWa(n-1);
    }

    public static void main(String[] args) {
        System.out.println(qingWa(3));
    }
}
